// #include <stdio.h>
// #include <stdlib.h>
// #include <windows.h>
// #define MAX_SIZE 100
//
// typedef struct {
//     int parent[MAX_SIZE];
//     int rank[MAX_SIZE];
//     int size;
// } DisjointSet;
//
// // 初始化（仅初始化前n个元素）
// void InitSet(DisjointSet* d, int n) {
//     d->size = n;
//     for (int i = 0; i < n; i++) {  // 修改：仅初始化前n个
//         d->parent[i] = i;
//         d->rank[i] = 0;
//     }
// }
//
// // 查找 + 路径压缩
// int find(DisjointSet* ds, int x) {
//     if (ds->parent[x] != x) {
//         ds->parent[x] = find(ds, ds->parent[x]);  // 递归压缩路径
//     }
//     return ds->parent[x];
// }
//
// // 按秩合并（优化方向统一）
// void Union(DisjointSet* ds, int x, int y) {
//     int root1 = find(ds, x);
//     int root2 = find(ds, y);
//     if (root1 == root2) return;
//
//     // 统一合并方向：小秩合并到大秩
//     if (ds->rank[root1] < ds->rank[root2]) {
//         ds->parent[root1] = root2;
//     } else if (ds->rank[root1] > ds->rank[root2]) {
//         ds->parent[root2] = root1;
//     } else {
//         ds->parent[root2] = root1;  // 统一方向
//         ds->rank[root1]++;          // 仅当秩相同时增加
//     }
// }
//
// int main() {
//     DisjointSet ds;
//     InitSet(&ds, 10);  // 初始化10个元素
//
//     // 合并操作
//     Union(&ds, 0, 1);  // 秩相同，0为根，rank[0]=1
//     Union(&ds, 2, 3);  // 秩相同，2为根，rank[2]=1
//     Union(&ds, 0, 2);  // 秩相同，0为根，rank[0]=2
//     Union(&ds, 4, 5);  // 秩相同，4为根，rank[4]=1
//
//     // 验证路径压缩
//     printf("find(3) = %d\n", find(&ds, 3));  // 应返回0，且parent[3]=0
//
//     return 0;
// }